/*
389. 找不同
给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

 

示例:

输入：
s = "abcd"
t = "abcde"

输出：
e

解释：
'e' 是那个被添加的字母。
*/
/**
 * 解法1：
 * 记录每个字符出现的次数，次数不同的就是新增的字符
 */
#include <string>
using namespace std;

class Solution
{
public:
    char findTheDifference(string s, string t)
    {
        if(s.size() == 0) return t[0];
        int base[26] = {0};
        int head[26] = {0};
        for(auto &ch : s) {
            base[ch - 'a']++;
        }
        for(auto &ch : t) {
            head[ch - 'a']++;
        }
        for(int i = 0; i < 26; i++) {
            if(base[i] != head[i]) return 'a' + i;
        }
        return 'a';
    }
};